문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 레인보우 테이블 (문단 편집) == 아이디어 == 그냥 가능한 모든 값들을 저장하면 되는 걸 굳이 왜 "레인보우 테이블"이라고 부르냐 하면, 레인보우 테이블은 '''계산 시간을 희생해서 공간을 압도적으로 줄일 수 있다'''. 이를테면 암호 하나를 찾는 시간을 10만배 늘리는 대신 테이블을 10만분의 1로 줄일 수 있는 것. 어차피 해시 함수는 10만배 느려져 봤자 밀리초 단위기도 하고, 레인보우 테이블에 저장되는 값 숫자 대비 찾을 암호 숫자가 매우 적기 때문에 쓸만한 것이다. [[파일:external/upload.wikimedia.org/600px-Rainbow_table1.svg.png]] ([[https://commons.wikimedia.org/wiki/File:Rainbow_table1.svg|원 이미지]], CC-by-sa 2.5로 배포됨) 레인보우 테이블에는 해시 함수 H 말고도 이 해시의 결과를 레인보우 테이블의 가능한 입력으로 변환해 주는 함수 R이 더 들어간다. 물론 R은 입력에 따라 다르고, 해시 함수와는 달리 원래 가능한 입력에 적절히 대응만 되기만 하면 된다. 다르게 생각하면, 레인보우 테이블은 H를 깨는 게 아니라 '''f(x) = R(H(x))인 f를 깬다'''. H와는 달리 f는 입력과 출력이 같기 때문에 다루기가 쉽다. 처음에 테이블을 만들 때는... 1. 가능한 입력 중 하나를 잡아서 H를 적용한다. 1. 함수의 결과를 R로 변환한다. 1. 이 과정을 필요한 숫자(k회라고 하자)만큼 반복한다. 1. 이제 입력 x와 마지막에 변환된 값 y = R(H(...R(H(x))...)) = f^^k^^(x)를 저장한다. 1. 이 작업을 최대한 많은 입력에 대해 반복한다. 여기서 중요한 점은, x와 y만 저장해도 계산만 좀 더 하면 f(x), f(f(x)), ..., f^^k-1^^(x)의 다른 k-1개의 입력이 커버된다는 것이다. 중간에 저장해야 할 게 k개에서 1개가 되었으니 공간이 1/k가 된다! 이 테이블을 써 먹으려면, 입력 a = H(b)가 있을 때 R(a), R(H(R(a))), ...를 계산해서 테이블의 y에 겹치는 게 있는지 보면 된다. 겹치는 게 있다면 대응되는 x로부터 최대 k번 f를 적용해서 b가 나오는지 확인해 보면 된다. (f(b) = f(c)인 c가 있을 수 있으므로 확인이 실패할 수 있다.) 안 나오면 그냥 한 번도 커버가 안 된 거고 나오면 잘 된 거다. [[참 쉽죠?]] ...실은 뻥이고, 이 방법은 치명적인 문제가 있는데 입력이 많이 들어가면 많이 들어갈 수록 f(x), f(f(x)) 등이 서로 충돌할 가능성이 높아진다. 한 번 충돌이 나는 입력이 나오면 거기서부터는 커버되는 입력들이 똑같으니까 공간 절약이 1/k에서 확 줄어들 수 있는데, 이런 (x, y) 쌍들을 걸러낼 수 없다! 예를 들어 "뿌뿌뽕"을 f에 세 번 돌린 것과 "용개"를 f에 다섯 번 돌린 게 같은 값이 나온다고 하자. 그러면 이 두 값이 커버하는 입력의 개수는 2k개가 아니라 k+5개[* "뿌뿌뽕", f("뿌뿌뽕") .. f^^2^^("뿌뿌뽕"), "용개", f("용개") .. f^^4^^("용개"), f^^3^^("뿌뿌뽕") = f^^5^^("용개"), .., f^^k^^("뿌뿌뽕") = f^^k+2^^("용개").] 밖에 안 되니까 도움이 안 된다. 이럴 바에는 둘 중 하나를 날려 버리면 좋겠는데 (x, y) 쌍만 가지고는 이걸 알 수 없다. [[파일:external/upload.wikimedia.org/600px-Rainbow_table2.svg.png]] ([[https://commons.wikimedia.org/wiki/File:Rainbow_table2.svg|원 이미지]], CC-by-sa 2.5로 배포됨) 그래서 '''진짜''' 레인보우 테이블은 각 단계별로 서로 다른 R을 쓴다(위 그림들에서 첨자가 붙어 있는 게 이 때문). 서로 다른 R을 쓰기 때문에 앞에서 "뿌뿌뽕"과 "용개"가 우연히 같은 값이 나왔어도 같은 위치에서 충돌이 난 게 아니면 서로 다른 입력을 커버하게 된다. 이 경우 커버하는 입력의 개수는 2k개에서 2k-1개로 줄어드는 수준으로, k가 크다면 무시해도 될 수준. 같은 위치에서 충돌이 나오면 그 뒤로는 같은 입력이 생성되긴 할텐데, 이러면 y가 겹칠테니 그냥 제거하면 된다. 이런 레인보우 테이블을 만들 가능성 자체를 없애기 위해 오늘날 암호를 저장할 때는 [[http://bcrypt.sourceforge.net/|bcrypt]]나 [[https://www.tarsnap.com/scrypt.html|scrypt]]와 같이 한 번 해시 함수를 적용하는 데 '''더럽게 오래 걸리는''' 함수를 써야 한다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기